package com.cjl.algorithm.sort

import com.cjl.algorithm.help.SortInt
import com.cjl.algorithm.help.text

/**
 * 冒泡排序 from 小灰的算法之旅
 *
 */
class BubbleSort: SortInt() {
    override fun sort(array: Array<Int>): Array<Int> {
        println("before ${array.text()}")
        // TODO 优化点 1，右侧边界有序部分不需要再次排序
        var lastIndex = 0
        val size = array?.size
        if (size > 1){
            var sortBorder = size-1
            for(j in 0 until size){
                //TODO  优化点 2,遍历后 未发生交换，说明当前已经有序
                var isSorted = true
                for(i in 0 until sortBorder/*size-1*/ ){
                    if (array[i] > array[i+1]){
                        array[i] = array[i+1].also { array[i+1] = array[i] }
                        isSorted = false
                        lastIndex = i
                    }
                }
                sortBorder = lastIndex
                if (isSorted){
                    break
                }
            }
        }
        return array
    }
}